package main.old.new_2023.last.month_7;


import java.util.Arrays;

/**
 * @Description: todo 931. 下降路径最小和
 * 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
 * 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
 * 具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
 *
 * todo 剑指 Offer 15. 二进制中1的个数
 * 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。
 * 提示：
 * 请注意，在某些语言（如 Java）中，没有无符号整数类型。
 * 在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
 * 在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
 *
 * todo 剑指 Offer 39. 数组中出现次数超过一半的数字
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * todo 剑指 Offer 40. 最小的k个数
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/
public class Solution0713 {

    //数组中出现次数超过一半的数字
    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr, 0, arr.length - 1);
        return Arrays.copyOf(arr, k);

    }
    //快速排序
    private void quickSort(int[] arr, int l, int r) {
        // 子数组长度为 1 时终止递归
        if (l >= r) return;
        // 哨兵划分操作（以 arr[l] 作为基准数）
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        // 递归左（右）子数组执行哨兵划分
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] matrix = {2,1,3,6,5,4,7,8,9};
        Solution0713 test = new Solution0713();
        int[] i = test.getLeastNumbers(matrix,3);
        System.out.println(i);
    }
    //数组中出现次数超过一半的数字
    public int majorityElement(int[] nums) {

        Arrays.sort(nums);
        return nums[nums.length/2];
    }

    // you need to treat n as an unsigned value
    //二进制中1的个数
    public int hammingWeight(int n) {
        //根据 与运算 定义，设二进制数字 nnn ，则有：
        //若 n&1=0 ，则 n 二进制 最右一位 为 0 ；
        //若 n&1=1，则 n 二进制 最右一位 为 1 。
        int sum = 0;
        while (n !=0){
            int i = n & 1;
            if (i == 1){
                sum++;
            }
            n >>>= 1;
        }
        return  sum;
    }


    //下降路径最小和
    //解决办法是递归，但是有重复的路径，即相同的dfs ，可以吧相同的dfs记录到 相同位置的 二元数组中，初始化二元数组，value特殊化
    int[][] ints;
    int[][] hashInts;
    int high,wight;
    public int minFallingPathSum(int[][] matrix) {
        ints = matrix;
        int sum = Integer.MAX_VALUE;
        high = matrix.length;
        wight = matrix[0].length;
        hashInts = new int[high][wight];
        for (int a = 0;a< high;a++){
            for (int b = 0;b<wight;b++){
                hashInts[a][b] = Integer.MIN_VALUE;
            }
        }
        for (int i = 0;i < wight;i++){
            int temp = dfs(high - 1, i);
//            int temp = dfs + matrix[high - 1][i];
            if (temp < sum){
                sum = temp;
            }
        }
        return sum;
    }
    private int dfs(int c,int n){
        if (n < 0 || n >= wight){
            return Integer.MAX_VALUE;
        }
        if (c == 0){
            return ints[c][n];
        }
        if (hashInts[c][n] != Integer.MIN_VALUE){
            return hashInts[c][n];
        }
        //三个方向的最小值
        int temp = Math.min(
                Math.min(dfs(c - 1, n - 1), dfs(c - 1, n)),
                dfs(c - 1, n + 1)) + ints[c][n];
        hashInts[c][n] = temp;
        return temp;
    }
}
